package cn.lucky.datastructure.linked;

/**
 * @author lingpeng.jiang
 * @create 2021-02-02-21:21
 *  双端链表的实现
 */
public class DoubleEndedLinkedListTest {


    public static void main(String[] args) {
        DoubleEndLinkedList doubleLinked = new DoubleEndLinkedList();
        doubleLinked.addHead("a");
        doubleLinked.addHead("b");
        doubleLinked.addHead("c");
        doubleLinked.addTail("e");
        doubleLinked.addTail("f");
        doubleLinked.addTail("g");
        doubleLinked.display();
        doubleLinked.removeByHead();
        doubleLinked.display();
        doubleLinked.removeByTail();
        doubleLinked.display();
    }

}

/**
 * 封装双端链表数据结构
 */
class DoubleEndLinkedList{

    /**
     * head pointer node
     */
    private Node head;

    /**
     * tail pointer Node
     */
    private Node tail;

    /**
     * linked list length
     */
    private int size;


    public DoubleEndLinkedList(){
        this.size = 0;
        this.head = null;
        this.tail = null;
    }


    /**
     * inner Node object
     */
    private static class Node{
        private Object data;
        private Node next;

        public Node(Object data){
            this.data = data;
            this.next = null;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "data=" + data +
                    ", next=" + next +
                    '}';
        }
    }


    /**
     * 从头部添加元素
     * @param data
     */
    public void addHead(Object data){
        if (size == 0){
            Node node = new Node(data);
            head = node;
            tail = head;
        }else{
            Node node = new Node(data);
            node.next = head;
            head = node;
        }
        size++;
    }


    /**
     * 从链表尾部添加元素
     * @param data
     */
    public void addTail(Object data){
        Node node = new Node(data);
        if (size == 0){
            head = node;
            tail = head;
        }else{
            tail.next = node;
            tail = tail.next;
        }
        size++;
    }


    /**
     * 删除头结点
     */
    public Object removeByHead(){
        Object data = head.data;
        head = head.next;
        size--;
        return data;
    }


    /**
     * 删除尾结点
     */
    public Object removeByTail(){
        Object data = tail.data;
        if (isEmpty()){
            throw new RuntimeException("this linked list is null");
        }else{
            Node tempNode = head;
            while (!tail.equals(tempNode.next)){
                tempNode = tempNode.next;
            }
            tempNode.next = null;
            tail = tempNode;
            size--;
        }
        return data;
    }


    /**
     * 查询链表中的元素
     * @param data
     * @return
     */
    public Node find(Object data){
        if (isEmpty()){
            throw new RuntimeException("this linked size is null");
        }
        Node current = head;
        int tempSize = size;
        while (tempSize > 0){
            if (data.equals(current.data)){
                return current;
            }else{
                current = current.next;
            }
            tempSize--;
        }
        return null;
    }


    /**
     * 判断是否为空链表
     * @return
     */
    public boolean isEmpty(){
        return size == 0;
    }


    /**
     * 遍历显示所有的节点的信息
     */
    public void display(){
        if (isEmpty()){
            System.out.println("[]");
        }else{
            Node current = head;
            int tempSize = size;
            if (tempSize == 1){
                System.out.print("[ " + head.data + " ]");
            }
            while (tempSize > 0){
                if (current == head){
                    System.out.print("[ " + current.data + "->");
                }else if (current.next == null){
                    System.out.print( current.data + " ]");
                }else{
                    System.out.print(current.data + "->");
                }
                tempSize--;
                current = current.next;
            }
            System.out.println();
        }
    }




}